package algorithm.test1Tree.test2BST;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinarySearchTree<E> {
    private int size;
    /**
     * 根节点
     */
    private Node<E> root;
    private Comparator comparator;


    public int size(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }
    public void clear(){

    }
    public void remove(E element){

    }
    public boolean contains(E element){
        return false;
    }
    
    public void add(E element){
        //一开始根节点是空的，所以第一个节点是根节点
        if(root==null){
            root=new Node(element,null);
            size++;
            return;
        }
        //添加的不是第一个节点那么照父节点（第一个是根节点）(默认情况下根节点是父节点也可以是null)
        Node<E> parent=root;
        Node<E> node=root;
        int cmp=0;
        while(node !=null){
            cmp = compare(element, node.element);
            //父节点
            parent=node;
            if(cmp>0){
                node=node.right;
            }else if(cmp<0){
                node=node.left;
            }else{//相等打话（说明插入了重复元素，有两种方法1，直接返回，2，替换旧值，这里先直接返回）
                return;
            }
        }
        Node<E> newNode=new Node(element,parent);
        //看看插入到父节点打左边还是右边
        if(cmp>0){//最后一次比较的结果
            parent.right=newNode;
        }else{
            parent.left=newNode;
        }
        size++;
    }





    /**
     * 前序遍历
     */
    public void cusPreOrder(){
        preOrder(root);
    }


    private void preOrder(Node<E> node){
        if(node==null){
            return;
        }
        System.out.println("前序遍历--当前节点。。。。"+node.element);
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 前序遍历非递归
     */
    void NoneRecurPreOrder(){

        Stack<Node> stack=new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node node=stack.pop();
            System.out.println(node.element);
            if(node.right !=null){
                stack.push(node.right);
            }
            if(node.left !=null){
                stack.push(node.left);
            }
        }
    }







    /**
     *2， 中序遍历 see readme.txt
     */
    public void cusMiddleOrder(){
        middleOrder(root);
    }


    private void middleOrder(Node<E> node){
        if(node==null){
            return;
        }
        middleOrder(node.left);
        System.out.println("中序遍历--当前节点。。。。"+node.element);
        middleOrder(node.right);
    }

    void noneRecurMidOrder(){

        if(root==null)return;
        Stack<Node<E>> stack = new Stack<>();
        Node<E> node = root;
        stack.push(node);

        while(!stack.isEmpty()) {
            //只要你有左孩子，就将左孩子压入栈中
            if(node!=null &&  node.left!=null) {
                stack.push(node.left);
                node = node.left;
            }else {
                node = stack.pop();//弹出栈顶节点  左孩子--->根节点
                System.out.print(node.element+" ");//访问
                if(node!=null && node.right!=null) {//如果栈点元素有右孩子的话，将有节点压入栈中
                    stack.add(node.right);
                    node = node.right;
                }else
                    node = null;//p=stk.pop;已经访问过p了，p设置为null
            }
        }
    }




    /**
     * 3,后序遍历
     */
    public void lastOrder(){
        lastOrderDiGui(root);
    }

    /**
     * 这个是先 left ,后right打印出来的元素是升序打，如果先 right后left 打印出来打元素就是降序打
     * 其他都不用改
     * @param node
     */
    private void lastOrderDiGui(Node<E> node){
        if(node==null){
            return;
        }
        lastOrderDiGui(node.left);
        lastOrderDiGui(node.right);
        System.out.println("后序遍历--当前节点。。。。"+node.element);
    }


    /**
     * 4，层序遍历 see,readme.txt
     */
    public void levelOrder(){
        if(root==null){
            return;
        }
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node node=queue.poll();//头节点出队
            System.out.println("层序遍历元素-----"+node.element);
            if(node.left !=null){
                queue.offer(node.left);
            }
            if(node.right !=null){
                queue.offer(node.right);
            }
        }
    }


    /**
     * 获取树的高度，递归的方式：（根节点的高度），高度指的是，根节点到
     * 最远的叶子节点的层数
     * @return
     */
    public int treeHeight(){
        return height(root);
    }

    public int height(Node node){
        if(node==null){
            return 0;
        }
        int left=height(node.left);
        int right=height(node.right);
        return Math.max(left,right)+1;

    }

    /**
     * 树的高度，非递归的方式
     * @return
     */
    public int treeHeight2(){
        if(root==null){
            return 0;
        }
        int heigth=0;
        //每一层的元素的数量，默认是1 个（根节点的）
        int levelSize=1;
        Queue<Node> queue=new LinkedList();
        queue.offer(root);

        while(!queue.isEmpty()){
            Node node=queue.poll();//头节点出队
            levelSize--;
            if(node.left !=null){
                queue.offer(node.left);
            }
            if(node.right !=null){
                queue.offer(node.right);
            }
            //levelSize==0说明当前层的元素访问完了，剩下的是下一层的元素
            if(levelSize==0){
                levelSize=queue.size();
                heigth++;
            }
        }
        return heigth;
    }

    /**
     * 判断是否是完全二叉树
     * @return
     */
    public boolean checkCompleteTree(){

        if(root==null){
            return false;
        }
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);

        boolean leaf=false;

        while(!queue.isEmpty()){
            Node node=queue.poll();//头节点出队
            //如果要求是叶子节点，但是不是叶子节点，返回false;
            if(leaf && !node.isleaf()){
                return false;
            }


            if(node.left !=null && node.right !=null){
                queue.offer(node.left);
                queue.offer(node.right);
            }else if(node.left==null && node.right !=null){
                return false;
            }else{//这里意味着后面遍历打节点都是叶子节点
                leaf=true;
                if(node.left !=null){
                    queue.offer(node.left);
                }
            }
        }
        return true;
    }









    /**
     * 判断空
     * @param elment
     */
    private void elementNotNullCheck(E elment){
        if(elment==null){
            throw new IllegalArgumentException("元素不能为空");
        }
    }

    /**
     * 返回值=0 表示e1=e2   返回值大于0 表示 e1>e2 返回值小于0表示 e1<e2
     * @param e1
     * @param e2
     * @return
     */
    private int compare(E e1,E e2){
        if(comparator !=null){
            return comparator.compare(e1,e2);
        }
        //E 要实现comparable接口
        return((Comparable)e1).compareTo(e2);
    }

  /*  private static class Node<E>{
        //节点存储打元素
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        //AVL树用来计算平衡因子（左子树的高度-右子树的高度）
        int height;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isleaf(){
            return left==null && right==null;
        }

        public boolean hasTwoChildren(){
            return left!=null && right!=null;
        }
    }*/
}
